# coding: utf-8

from graph import (
    Subgraph,
    edge_map,
    vertex_map,
    INVALID_EDGE,
    INVALID_VERTEX,
    vertex_t,
    Hierarchy,
)
from collections import deque
from typing import Iterator, Iterable, Sequence, Union
from functools import cmp_to_key


class OutNeighboursIterator:
    g: Subgraph
    data: Iterable[vertex_t]
    index: int

    def __init__(self, g: Subgraph):
        self.g = g
        self.index = 0
        self.data = []

    def clone(self) -> "DoubleOutNeighboursIterator":
        """克隆当前迭代器"""
        return OutNeighboursIterator(self.g)

    def init(self, v: vertex_t):
        self.index = 0
        self.v = v
        self.data.clear()
        self.data.extend(self.g.out_neighbours(v))

    def __iter__(self) -> Iterator[vertex_t]:
        return self

    def __next__(self) -> vertex_t:
        if self.index < len(self.data):
            result = self.data[self.index]
            self.index += 1
            return result
        else:
            raise StopIteration


"""
双端出边节点选择器
"""


class DoubleOutNeighboursIterator:
    g: Subgraph  # 原图
    h: Hierarchy  # 层次图
    # v: vertex_t  # 节点
    isLeftOrRight: bool  # 顺序或者逆序
    index: int  # 当前索引
    data: Iterable[vertex_t]  # 出边节点列表

    def __init__(self, g: Subgraph, h: Hierarchy):
        self.g = g
        self.h = h
        self.index = 0
        self.isLeftOrRight = True
        self.data = []

    def clone(self) -> "DoubleOutNeighboursIterator":
        """克隆当前迭代器"""
        other = DoubleOutNeighboursIterator(self.g, self.h)
        # other.v = self.v
        other.isLeftOrRight = self.isLeftOrRight
        return other

    def init(self, v: vertex_t):
        self.index = 0
        self.v = v
        self.data.clear()
        self.data.extend(self.g.out_neighbours(v))
        # 重排节点序列
        self.data.sort(key=cmp_to_key(lambda v1, v2: self.__cmp_vertex_pos(v1, v2)))

    def changeDirection(self, flag: bool):
        if flag:
            # 表示只变换顺序或逆序，表示搜索过程中，“源点”和“汇点”没有变化，只是左右弧在变化
            self.isLeftOrRight = not self.isLeftOrRight
        else:
            # 顺序,表示搜索过程中，“源点”和“汇点”发生变化，需要重置为默认值
            self.isLeftOrRight = True

    def __iter__(self):
        return self

    def __next__(self):
        if self.index < len(self.data):
            result = self.data[self.index]
            self.index += 1
            return result
        else:
            raise StopIteration

    def __cmp_vertex_pos(self, v1: vertex_t, v2: vertex_t) -> int:
        # 根据层次结构中的位置比较两个顶点
        # if self.isLeftOrRight:
        #     return self.h.get_pos(v1) < self.h.get_pos(v2)
        # else:
        #     return self.h.get_pos(v1) > self.h.get_pos(v2)
        p1 = self.h.get_pos(v1)
        p2 = self.h.get_pos(v2)
        if p1 < p2:
            # 正序里 p1<p2 => v1 更靠前，返回 -1；逆序则返回 +1
            return -1 if self.isLeftOrRight else 1
        elif p1 > p2:
            # 正序里 p1>p2 => v1 更靠后，返回 +1；逆序则返回 -1
            return 1 if self.isLeftOrRight else -1
        else:
            return 0


def add_vertex_to_list(v: vertex_t, lst: Sequence[vertex_t]):
    if len(lst) == 0:
        lst.append(v)
    elif v is not lst[0]:
        # 避免成环
        lst.append(v)
    return lst


def remove_vertex_from_list(v: vertex_t, lst: Sequence[vertex_t]):
    try:
        lst.remove(v)
    except:
        pass
    return lst


class Lpm:
    """
    属性定义
    predecessor --  节点的前节点
    isVisited   --  节点是否被访问
    isDrawed    --  分支是否被着色（被绘制）
    layer       --  节点所在层次（也表示节点的最长路径）
    globalLayer --  节点所在的层次（★★★全局静态的数据，固定不变）
    inDegree    --  节点的实际入度（与节点的入边被着色的情况有关，如果入边分支全部着色，则实际入度为0）
    outDegree   --  节点的实际出度（同上）
    """

    pred: vertex_map[vertex_t]
    is_visited: vertex_map[bool]
    is_drawed: edge_map[bool]
    layer: vertex_map[int]
    global_layer: vertex_map[int]
    indeg: vertex_map[int]
    outdeg: vertex_map[int]
    g: Subgraph

    def __init__(self, g: Subgraph):
        self.g = g
        self.pred = vertex_map(g, "pred", INVALID_VERTEX)
        self.is_visited = vertex_map(g, "is_visited", False)
        self.layer = vertex_map(g, "layer", 0)
        self.global_layer = vertex_map(g, "global_layer", 0)
        self.indeg = vertex_map(g, "indeg", lambda v: g.in_degree(v))
        self.outdeg = vertex_map(g, "outdeg", lambda v: g.out_degree(v))
        self.is_drawed = edge_map(g, "is_drawed", False)

    # 原最长路径法有错误，需要做如下修正：
    # 当从节点v从队列出队的时候，将isVisited属性还原为false
    def assignLayerNumToVertex(
        self,
        source: vertex_t,
        iterator: Union[OutNeighboursIterator, DoubleOutNeighboursIterator],
    ):
        self.is_visited.init()
        self.pred.init(val = INVALID_VERTEX)

        q = deque()
        q.append(source)  # 入队
        self.is_visited[source] = True  # 出发节点设置未被访问过
        iterator2 = iterator.clone()  # 克隆迭代器
        while len(q) > 0:
            v = q[0]  # 取出首元素
            iterator.init(v)  # 初始化迭代器
            for w in iterator:
                e = self.g.get_edge(v, w)
                if self.is_drawed[e]:
                    continue

                if self.is_visited[w]:
                    # 已被访问
                    if self.layer[w] < self.layer[v] + 1:
                        self.pred[w] = v
                        wlength = self.layer[v]
                        self.layer[w] = wlength + 1
                        iterator2.init(w)  # 初始化迭代器
                        for f in iterator2:
                            if self.pred[f] == w:
                                self.layer[f] = wlength + 2
                else:
                    # 未被访问
                    q.append(w)
                    self.is_visited[w] = True
                    self.pred[w] = v
                    self.layer[w] = self.layer[v] + 1
            self.is_visited[v] = False
            q.popleft()

    def global_seach_longest_path(self):
        # 查找源点
        # TODO: 当前未处理多源多汇, 可能存在多个源点汇点
        source = self.g.get_source()
        if source == INVALID_VERTEX:
            raise ValueError("No source vertex found in the graph.")
        # 执行最长路径法分层
        self.assignLayerNumToVertex(source, OutNeighboursIterator(self.g))
        # 复制属性
        for v in self.g.get_all_nodes():
            self.global_layer[v] = self.layer[v]

    def search_longest_path(
        self,
        source: vertex_t,
        target: vertex_t,
        iterator: Union[OutNeighboursIterator, DoubleOutNeighboursIterator],
    ) -> Sequence[vertex_t]:
        """
        查找从source到所有顶点的最长路径
        """
        self.assignLayerNumToVertex(source, iterator)
        path = []
        if self.pred[target] != INVALID_VERTEX:
            v = target
            while v != INVALID_VERTEX:
                path.append(v)
                v = self.pred[v]
            # TODO 应考虑到源点可能不是path[0]的情况
            # 例如：如果源点是source，且source不是path[0]，
            # if len(path) == 0 or path[-1] != source:
            #     path.clear()
            # else:
            path.reverse()
        return path

    def color_longest_path(self, path: Sequence[vertex_t]):
        """
        将最长路径上的边着色
        """
        for i in range(len(path) - 1):
            s, t = path[i], path[i + 1]
            e = self.g.get_edge(s, t)
            if e != INVALID_EDGE:
                # 着色分支（s，t）中s的出度-1，t的入度-1
                self.is_drawed[e] = True
                self.outdeg[s] -= 1
                self.indeg[t] -= 1

    def analyse_vertex_in_longest_path(
        self, v: vertex_t, sources: Sequence[vertex_t], targets: Sequence[vertex_t]
    ) -> bool:
        if self.is_all_vertex_inEdges_drawed(v) and self.is_all_vertex_outEdges_drawed(
            v
        ):
            remove_vertex_from_list(v, sources)
            remove_vertex_from_list(v, targets)
        elif self.is_all_vertex_inEdges_drawed(v):
            add_vertex_to_list(v, sources)
        elif self.is_all_vertex_outEdges_drawed(v):
            add_vertex_to_list(v, targets)

    #  changes:
    #  1、经过分析，我发现所谓的节点分析过程实质上可以等价于程序的编写者将他的画图思想融入到算法过程中
    #  2、我的画图思想：在发现一条路径之后，每次都尝试在路径中最远的2个节点之间寻找路径，并绘制路径
    #  3、找到一条路径之后，将节点按照路径的反向顺序加入到sources和targets中，
    #  	这就等价于“尝试在路径中最远的2个节点之间寻找路径”思想
    def analyse_longest_path(
        self,
        path: Sequence[vertex_t],
        sources: Sequence[vertex_t],
        targets: Sequence[vertex_t],
    ):
        """
        分析最长路径上的顶点
        """
        for v in path:
            self.analyse_vertex_in_longest_path(v, sources, targets)

    def remove_vertex_on_longest_path(
        self,
        path: Sequence[vertex_t],
        sources: Sequence[vertex_t],
        targets: Sequence[vertex_t],
    ):
        for v in path:
            if self.is_all_vertex_inEdges_drawed(
                v
            ) and self.is_all_vertex_outEdges_drawed(v):
                # 如果顶点v的所有入边和出边都被着色，则从sources和targets中移除
                remove_vertex_from_list(v, sources)
                remove_vertex_from_list(v, targets)

    def add_vertex_to_sources(
        self, path: Sequence[vertex_t], sources: Sequence[vertex_t]
    ):
        """
        将路径中的顶点添加到sources中
        """
        for v in path:
            if self.is_all_vertex_inEdges_drawed(
                v
            ) and not self.is_all_vertex_outEdges_drawed(v):
                # 如果顶点v的所有入边都被着色，则添加到sources中
                add_vertex_to_list(v, sources)

    def add_vertex_to_targets(
        self, path: Sequence[vertex_t], targets: Sequence[vertex_t]
    ):
        """
        将路径中的顶点添加到sources中
        """
        for v in path:
            if self.is_all_vertex_outEdges_drawed(
                v
            ) and not self.is_all_vertex_inEdges_drawed(v):
                # 如果顶点v的所有出边都被着色，则添加到targets中
                add_vertex_to_list(v, targets)

    def revised_analyse_longest_path(
        self,
        path: Sequence[vertex_t],
        sources: Sequence[vertex_t],
        targets: Sequence[vertex_t],
    ):
        # 实现功能描述：
        # 1、对sources按照顺序加入
        # 2、对targets按照逆序加入
        # 3、删除入边和出边全部着色的节点
        self.remove_vertex_on_longest_path(path, sources, targets)
        self.add_vertex_to_sources(path, sources)
        self.add_vertex_to_targets(path, targets)

    def printEdgeDrawed(self):
        """
        打印所有边的着色状态
        """
        print("\n始点\t->\t末点\t\t着色情况\n")

        for e in self.g.get_all_edges():
            u, v = self.g.get_edge_uv_tuple(e)
            print(f"{u}\t->\t{v}\t\t{'已被着色' if self.is_drawed[e] else '未被着色' }")

    def printSourcesAndTargets(
        self, sources: Sequence[vertex_t], targets: Sequence[vertex_t]
    ):
        """
        打印sources和targets
        """
        print("sources:", end="")
        if len(sources) == 0:
            print("null", end="")
        else:
            print(f" {','.join([str(v) for v in sources])}", end="")
        print("\t\ttargets: ", end="")

        if len(targets) == 0:
            print("null", end="")
        else:
            print(f" {','.join([str(v) for v in targets])}", end="")
        print()

    def printPath(self, path: Sequence[vertex_t]):
        """
        打印路径
        """
        print("Path: ", end="")
        if len(path) == 0:
            print("null", end="")
        else:
            print(" ".join([str(v) for v in path]))

    def is_all_vertex_outEdges_drawed(self, v: vertex_t) -> bool:
        """
        判断顶点v的所有出边是否都被着色
        """
        return self.outdeg[v] == 0

    def is_all_vertex_inEdges_drawed(self, v: vertex_t) -> bool:
        """
        判断顶点v的所有入边是否都被着色
        """
        return self.indeg[v] == 0

    def getTotalLayerNum(self) -> int:
        """
        获取图的总层数
        """
        return max(self.global_layer.values()) + 1

    def getVertexLayerNum(self, v: vertex_t) -> int:
        """
        获取顶点v的层数
        """
        return self.global_layer[v]

    # 这里出度和入度概念是经过改造的
    # 主要是应对 “ 并联通路 ” 中出现 “ 并联通路 ” 的情况（嵌套并联通路）
    # 方法：查找v、w的 “ 出度 ” 和 “ 入度 ” （这里的出度和入度是在原有图的出度和入度的概念上改造）
    # 若该节点的出度为3，出边有2条分支着色，则“实际出度”为1； “ 入度 ” 的概念同上
    # 在着色的过程中，动态的修改节点的“出度”和“入度”
    def actualInDegree(self, v: vertex_t) -> int:
        """
        获取顶点v的实际入度
        """
        return self.indeg[v]

    def actualOutDegree(self, v: vertex_t) -> int:
        """
        获取顶点v的实际出度
        """
        return self.outdeg[v]

    def getLayerGap(self, v: vertex_t, w: vertex_t) -> int:
        """
        获取顶点v的层间隙
        """
        return self.global_layer[w] - self.layer[v]
